﻿#define  _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//
//自除数 是指可以被它包含的每一位数整除的数。
//
//例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
//自除数 不允许包含 0 。
//
//给定两个整数 left 和 right ，返回一个列表，列表的元素是范围[left, right] 内所有的 自除数 。
//
//示例 1：
//
//输入：left = 1, right = 22
//输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
//示例 2:
//
//输入：left = 47, right = 85
//输出：[48, 55, 66, 77]
//

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//
//int* selfDividingNumbers(int left, int right, int* returnSize) {
//    int* ret = (int*)calloc((right - left + 1), 4);
//    if (ret == NULL)
//    {
//        exit(-1);
//    }
//    int i = 0;
//    int count = 0;
//    for (i = left; i <= right; i++)
//    {
//        int flag = 1;
//        int num = i;
//        while (num)
//        {
//            if (num % 10 == 0)
//            {
//                flag = 0;
//                break;
//            }
//            else
//            {
//                if (i % (num % 10) == 0)
//                {
//                    num = num / 10;
//                }
//                else
//                {
//                    flag = 0;
//                    break;
//                }
//            }
//        }
//        if (flag == 1)
//        {
//            ret[count] = i;
//            count++;
//        }
//    }
//    *returnSize = count;
//    if (count > 0)
//    {
//        int* ptr = (int*)realloc(ret, count * 4);
//        if (ptr == NULL)
//        {
//            exit(-1);
//        }
//        ret = ptr;
//        return ret;
//    }
//    free(ret);
//    return NULL;
//}
//
//int main()
//{
//    int count = 0;
//    int* ret = selfDividingNumbers(25, 25, &count);
//    if (count > 0&&ret!=NULL)
//    {
//        for (int i = 0; i < count; i++)
//        {
//            printf("%d ", ret[i]);
//        }
//        free(ret);
//    }
//    int num = 0;
//
//
//    return 0;
//}


//给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
//
//题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
//
//请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
//
//
//
//示例 1:
//
//输入: nums = [1, 2, 3, 4]
//输出 : [24, 12, 8, 6]
//示例 2 :
//
//	输入 : nums = [-1, 1, 0, -3, 3]
//	输出 : [0, 0, 9, 0, 0]
//
//int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
//    1.要考虑数组中0的数量，超过1个0的全部返回0
//    *returnSize = numsSize;
//    int* ret = (int*)calloc(numsSize, 4);
//    if (ret == NULL)
//    {
//        exit(-1);
//    }
//    int mulsum = 1;
//    int count = 0;//统计0的数量
//    int i = 0;
//    for (i = 0; i < numsSize; i++)
//    {
//        if (count > 1)
//        {
//            0的数量大于1，直接返回全0数组
//            break;
//        }
//        if (nums[i] == 0)
//        {
//            count++;
//
//        }
//        else
//        {
//            mulsum *= nums[i];
//        }
//    }
//    if (count == 1)
//    {
//        for (i = 0; i < numsSize; i++)
//        {
//            if (nums[i] == 0)
//            {
//                ret[i] = mulsum;
//            }
//            else
//            {
//                ret[i] = 0;
//            }
//        }
//    }
//    else if (count == 0)
//    {
//        for (i = 0; i < numsSize; i++)
//        {
//            ret[i] = mulsum / nums[i];
//        }
//    }
//    return ret;
////}
//
//int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
//    int* ret = (int*)calloc(numsSize, 4);
//    if (ret == NULL)
//    {
//        exit(-1);
//    }
//    int i = 0;
//    // 1.将数组遍历一遍，把该坐标的左边的数的乘积填入返回数组中
//
//     //求左乘积从前往后遍历
//    int leftsum = 1;
//    for (i = 0; i < numsSize; i++)
//    {
//        if (i == 0)
//        {
//            ret[i] = leftsum;
//        }
//        else
//        {
//            leftsum *= nums[i - 1];
//            ret[i] = leftsum;
//        }
//    }
//
//    // 2.再将数组遍历一遍，将该坐标的右边的成绩乘进返回数组对应的左边乘积去
//
//     //求右乘积从后往前遍历
//    int rightsum = 1;
//    for (i = numsSize - 1; i >= 0; i--)
//    {
//        if (i == numsSize - 1)
//        {
//            ret[i] *= rightsum;
//        }
//        else
//        {
//            rightsum *= nums[i + 1];
//            ret[i] *= rightsum;
//        }
//    }
//    *returnSize = numsSize;
//    return ret;
//
//}



//写一个函数，求两个整数之和，要求在函数体内不得使用 + 、 - 、 * 、 / 四则运算符号。
//数据范围：两个数都满足−10≤n≤1000
//进阶：空间复杂度O(1)，时间复杂度O(1)

//int Add(int num1, int num2) {
//    // write code here
//    long long ret = 0;
//    int i = 0;
//    for (i = 0; i < 32; i++)
//    {
//        if ((((num1 >> i) & 1) & ((num2 >> i) & 1)) == 1)//两个数的这一位都为1
//        {
//            //判断ret的这一位是否为1
//            if (((ret >> i) & 1) == 1)
//            {
//                ret |= (1 << (i + 1));//高位进位
//            }
//            else {
//                ret |= (1 << (i + 1));//高位进位
//                ret &= (~(int)(pow(2, i))); //本位置零
//            }
//        }
//        else if ((((num1 >> i) & 1) | ((num2 >> i) & 1)) == 1)//其中一个数的这一位为1
//        {
//            if (((ret >> i) & 1) == 1)
//            {
//                ret |= (1 << (i + 1));//高位进位
//                ret &= (~(int)(pow(2, i))); //本位置零
//            }
//            else {
//                ret |= (1 << (i));//本位置为1
//            }
//        }
//        else//两个数的这一位都为0
//        {
//            //什么也不干
//            ;
//        }
//    }
//    //二进制进位的时候，然后两个数相加为正数，已经不用管了，得到了结果。
//    //如果两个数为负数的时候，要把符号位变成1
//    if ((((num1 >> 31) & 1) & ((num2 >> 31) & 1)) == 1)//最后确定符号位
//    {
//        ret |= (1 >> 31);//符号位先确定.
//    }
//    return (int)ret;
//}

//
//给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间[1, n] 内。
//请你找出所有在[1, n] 范围内但没有出现在 nums 中的数字，
//并以数组的形式返回结果。
//
//int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
//    int* arr = (int*)calloc(numsSize + 1, 4);
//    if (arr == NULL)
//    {
//        exit(-1);
//    }
//    int i = 0;
//    for (i = 1; i <= numsSize; i++)
//    {
//        arr[i] = 0;
//    }
//    int* ret = (int*)calloc(numsSize, 4);
//    if (ret == NULL)
//    {
//        exit(-1);
//    }
//    for (i = 0; i < numsSize; i++)
//    {
//        arr[nums[i]] = 1;
//    }
//    int count = 0;
//    for (i = 1; i <= numsSize; i++)
//    {
//        if (arr[i] == 0)
//        {
//            ret[count++] = i;
//        }
//    }
//    *returnSize = count;
//    free(arr);
//    if (count != 0)
//    {
//        int* ptr = (int*)realloc(ret, count * 4);
//        if (ptr == NULL)
//        {
//            exit(-1);
//        }
//        ret = ptr;
//        return ret;
//    }
//    return NULL;
//
//}






    //int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) 
    //{
    //    //不申请额外空间的做法就只能对数组本身操作
    //    //有一个区分的方法，由于数组元素和数组大小都是n
    //    //遍历一遍，数组的元素作为下标，找到对应的元素给它加上一个数组大小numsSize
    //    //更简单的方法，把这个数乘个-1变成他的负数（不要多次乘），要用的时候再乘-1来用
    //    //第一遍遍历的时候如果数组元素大于numsSize，就取莫，知道下标合法
    //    //再遍历一遍找到数组元素小于numsSize的下标，这些下标就是缺失的数
    //    //下标为0代表数字1，以此类推

    //    int* ret = calloc(numsSize, 4);
    //    if (ret == NULL)
    //    {
    //        exit(-1);
    //    }

    //    int count = 0;
    //    int i = 0;
    //    for (i = 0; i < numsSize; i++)
    //    {
    //        if (nums[i] < numsSize)
    //        {
    //            nums[nums[i] - 1] += numsSize;
    //        }
    //        else
    //        {
    //            int n = nums[i] - 1;
    //            while (n >= numsSize)//确保n的范围作为下标有效，找nums[i]的原始值
    //            {
    //                n %= numsSize;
    //            }
    //            nums[n] += numsSize;
    //        }
    //    }
    //    for (i = 0; i < numsSize; i++)
    //    {
    //        if (nums[i] <= numsSize)
    //        {
    //            ret[count] = i + 1;
    //            count++;
    //        }
    //    }
    //    *returnSize = count;
    //    if (count == 0)
    //    {
    //        free(ret);
    //        return NULL;
    //    }
    //    return ret;
    //}
//
//
//int main()
//{
//    int arr[8] = {4,3,2,7,8,2,3,1 };
//    int count = 0;
//    int*ret=findDisappearedNumbers(arr, 8, &count);
//    if (ret != NULL)
//    {
//        int i = 0;
//        for (i = 0; i < count; i++)
//        {
//            printf("%d ", ret[i]);
//        }
//        free(ret);
//    }
//
//    return 0;
//}



//给定一个二进制数组 nums ， 计算其中最大连续 1 的个数


//int findMaxConsecutiveOnes(int* nums, int numsSize) {
//
//    int i = 0;
//    int* arr = (int*)calloc(numsSize, 4);
//    if (arr == NULL)
//    {
//        exit(-1);
//    }
//    int count = 0;
//    int j = 0;//统计计数数组元素个数
//    for (i = 0; i < numsSize; i++)
//    {
//        if (nums[i] == 1)
//        {
//            count = count + 1;
//        }
//        else
//        {
//            arr[j] = count;
//            j++;
//            count = 0;//重新计数
//        }
//    }
//
//    arr[j] = count;//数组结束还要记录一次,如果数组中一个1也没有，也会将0记录
//    j++;//至少是1
//
//    int max = 0;
//    for (i = 0; i < j; i++)
//    {
//        if (arr[i] > max)
//        {
//            max = arr[i];
//        }
//    }
//    free(arr);
//    arr = NULL;
//    return max;
//
//    /*
//        int max=0;
//    int count=0;
//    int i=0;
//    for(i=0;i<numsSize;i++)
//    {
//        if(nums[i]==1)
//        {
//            count++;
//        }
//        else{
//            if(count>max)
//            {
//                max=count;
//            }
//            count=0;
//        }
//    }
//    if(max<count)
//    {
//        max=count;
//    }
//    return max;
//    */
//}
//
//int main()
//{
//    int arr[10] = { 1,1,0,1,1,1,1,0,1,0 };
//    int ret = findMaxConsecutiveOnes(arr, 6);
//    printf("%d\n", ret);
//
//    return 0;
//}


//完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。
//它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。
//例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1 + 2 + 4 + 7 + 14 = 28。
//输入n，请输出n以内(含n)完全数的个数。
//数据范围：1≤n≤5×10^5
//
//#include <stdio.h>
//#include<math.h>
//
//int main() {
//    int n = 0;
//    scanf("%d", &n);
//    int i = 1;
//    int count = 0;
//    for (i = 2; i <= n; i++)//1不是完美数
//    {
//        int sum = 1;
//        int j = 0;
//        for (j = 2; j < sqrt(i); j++)
//        {
//            if (i % j == 0)
//            {
//                sum = sum + j;
//                if(j!=sqrt(i))
//                {
//                  sum+=i/j;          
//                }
//            }
//        }
//        if (sum == i)
//        {
//            count++;
//        }
//    }
//    printf("%d\n", count);
//
//    return 0;
//}

//
//输入一个整数，将这个整数以字符串的形式逆序输出
//程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001
//
//数据范围:0≤n≤2^30
//
//输入描述：
//输入一个int整数
//
//输出描述：
//将这个整数以字符串的形式逆序输出

//#include <stdio.h>
//#include <string.h>
//#include<assert.h>
//void strreverse(char* str, int len)
//{
//    assert(str);
//    int left = 0;
//    int right = len - 1;
//    while (left < right)
//    {
//        char ch = str[left];
//        str[left] = str[right];
//        str[right] = ch;
//        left++;
//        right--;
//    }
//}
//
//int main() {
//    char str[100];
//    scanf("%s", str);
//    int len = strlen(str);
//    strreverse(str, len);
//    printf("%s\n", str);
//    return 0;
//}


//对字符串中的所有单词进行倒排。
//
//说明：
//
//1、构成单词的字符只有26个大写或小写英文字母；
//
//2、非构成单词的字符均视为单词间隔符；
//
//3、要求倒排后的单词间隔符以一个空格表示；如果原字符串中相邻单词间有多个间隔符时，倒排转换后也只允许出现一个空格间隔符；
//
//4、每个单词最长20个字母；
////
//
//#include <stdio.h>
//#include<string.h>
//#include<assert.h>
//#include<ctype.h>
//
//void reverse(char* left, char* right)
//{
//    assert(left && right);
//    while (left < right)
//    {
//        char ch = *left;
//        *left = *right;
//        *right = ch;
//        left++;
//        right--;
//    }
//
//}
//
//int main() {
//    char str[10001] = { 0 };
//    int i = 0;
//    char ch;
//    int flag = 0;
//    while ((ch = getchar()) != EOF)
//    {
//        if (isalpha(ch))
//        {
//            str[i++] = ch;
//            flag = 1;
//        }
//        else
//        {
//            if (flag == 1)
//            {
//                if (ch != '\n')
//                {
//                    str[i++] = ' ';
//                    flag = 0;
//                }
//
//            }
//        }
//    }
//    int len = strlen(str);
//    reverse(str, str + len - 1);
//    char* begin = str;
//    char* end = str;
//    while (*end != '\0')
//    {
//        begin = end;
//        if (isalpha(*end))
//        {
//            while (isalpha(*end))
//            {
//                end++;
//            }
//            reverse(begin, end - 1);
//        }
//        else {
//            end++;
//        }
//    }
//    printf("%s", str);
//    return 0;
//}